package main

import "strconv"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var m map[string]int
var result []*TreeNode

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	m = make(map[string]int)
	result = make([]*TreeNode, 0)
	traverse(root)
	return result
}

func traverse(root *TreeNode) string {
	if root == nil {
		return "-"
	}
	leftDesc := traverse(root.Left)
	rightDesc := traverse(root.Right)
	desc := leftDesc + "." + rightDesc + "." + strconv.Itoa(root.Val)
	if count := m[desc]; count == 1 {
		result = append(result, root)
	}
	m[desc]++
	return desc
}

func main() {
	root := &TreeNode{}
	n1 := &TreeNode{Val: 2}
	n2 := &TreeNode{Val: 3}
	n3 := &TreeNode{Val: 4}
	n4 := &TreeNode{Val: 2}
	n5 := &TreeNode{Val: 4}
	n6 := &TreeNode{Val: 4}
	root.Left = n1
	root.Right = n2
	n1.Left = n3
	n2.Left = n4
	n4.Left = n5
	n2.Right = n6
	ret := findDuplicateSubtrees(root)
	println(ret)
}
